package com.wtgroup.demo.mianshi.算法.图;

import lombok.AllArgsConstructor;

import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/5 22:11
 */
public class Q_Dijkstra {

    public static void main(String[] args) {
        加强堆<String> heapMap = new 加强堆<>();
        heapMap.put("z", 55);
        heapMap.put("b", 6);
        heapMap.put("c", 400);
        System.out.println(heapMap.priorityQueue.poll());
        System.out.println(heapMap.priorityQueue.poll());
        System.out.println(heapMap.priorityQueue.poll());
    }

    static class D1 {
        Map<Node, Integer> doit(Graph graph, Node start) {
            Collection<Node> nodes = graph.nodes.values();
            Set<Node> mark = new HashSet<>();
            HashMap<Node, Integer> dynamicWgtMap = new HashMap<>();
            dynamicWgtMap.put(start, 0);

            Map.Entry<Node, Integer> minEntry = getMinWgtAndUnmark(dynamicWgtMap, mark);
            while (minEntry != null) {
                for (Edge edge : minEntry.getKey().edges) {
                    Node to = edge.to;
                    int w = minEntry.getValue() + edge.weight;
                    Integer wgt = dynamicWgtMap.get(to);
                    if (wgt == null || wgt > w) {
                        dynamicWgtMap.put(to, w);
                    }
                }
                mark.add(minEntry.getKey());
            }


            return dynamicWgtMap;
        }

        private Map.Entry<Node, Integer> getMinWgtAndUnmark(HashMap<Node, Integer> dynamicWgtMap, Set<Node> mark) {
            int min = Integer.MAX_VALUE;
            Map.Entry<Node, Integer> ret = null;
            for (Map.Entry<Node, Integer> entry : dynamicWgtMap.entrySet()) {
                if (entry.getValue() < min && mark.contains(entry.getKey()) == false) {
                    min = entry.getValue();
                    ret = entry;
                }
            }

            return ret;
        }
    }

    @AllArgsConstructor
    static class Tup {
        Node node;
        int weight;
    }

    /**
     * @author nisus
     * @version 0.1
     * @since 2023/5/5 23:20
     */
    public static class 加强堆<K> {

        HashMap<K, Integer> node2WeightMap = new HashMap<>();
        PriorityQueue<K> priorityQueue = new PriorityQueue<>(new Comparator<K>() {
            @Override
            public int compare(K o1, K o2) {
                Integer w1 = node2WeightMap.get(o1);
                Integer w2 = node2WeightMap.get(o2);
                if (w1 != null && w2 != null) {
                    return w1 - w2;
                } else if (w1 != null) {
                    return w1;
                } else if (w2 != null) {
                    return w2;
                }
                return 0;
            }
        });

        void put(K key, Integer wgt) {
            Integer old = node2WeightMap.put(key, wgt);
            if (old == null) {
                priorityQueue.add(key);
            }
        }

        K poll() {
            return priorityQueue.poll();
        }
    }
}
